#include<bits/stdc++.h>
using namespace std;
inline void read(long long &x)
{
    x=0;long long f=1;
    char c=getchar();
    for(;!isdigit(c);c=getchar())
    {
        if(c=='-')
        f=-1;
    }
    for(;isdigit(c);c=getchar())
    x=(x<<3)+(x<<1)+(long long)(c)-48;
    x*=f;
}
const int N=1e6+10;
const int M=1e6;
struct node{
    int ls,rs;
    long long ma;
}h[N];
long long f[N],dp[N],ans=0;
long long a[N],n,T,code=1;
int ha[N],fa[N];
void init(int code)
{
    h[code].ls=h[code].rs=0;
    h[code].ma=-1e13;
}
void push_up(int p)
{
    h[p].ma=-1e13;
    if(h[p].ls!=0)
    h[p].ma=max(h[h[p].ls].ma,h[p].ma);
    if(h[p].rs!=0)
    h[p].ma=max(h[h[p].rs].ma,h[p].ma);
}
void query(int l,int r,int p,int mb)
{
    if(l==r)
    {
        ans=h[p].ma;
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=mb)
    query(l,mid,h[p].ls,mb);
    else
    query(mid+1,r,h[p].rs,mb);
}
void add(int l,int r,int p,int mb,long long val,int i)
{
    if(l==r)
    {
        if(val>h[p].ma)
            fa[mb]=i;
        h[p].ma=max(h[p].ma,val);
        return ;
    }
    int mid=(l+r)>>1;
    if(mid>=mb)
    {
        if(h[p].ls==0)
        {
            code++;
            h[p].ls=code;
            init(code);
        }
        add(l,mid,h[p].ls,mb,val,i);
    }
    else
    {
        if(h[p].rs==0)
        {
            code++;
            h[p].rs=code;
            init(code);
            
        }
        add(mid+1,r,h[p].rs,mb,val,i);
    }
    push_up(p);
}
int main()
{
    freopen("color.in","r",stdin);
    freopen("color.out","w",stdout);
    read(T);
    while(T--)
    {
        for(int i=1;i<=n;i++)
        dp[i]=f[i]=a[i]=fa[i]=0;
        for(int i=1;i<=code;i++)
            h[i].ls=h[i].rs=h[i].ma=0;
        code=1;
        read(n);
        for(int i=1;i<=n;i++)
        {
            read(a[i]);
            if(a[i]==a[i-1])
            f[i]=f[i-1]+a[i];
            else
            f[i]=f[i-1];
        }
        long long prt=0;
        for(int i=1;i<=n;i++)
        {
            if(ha[a[i]]==T+1)
            {
                query(1,M,1,a[i]);
                dp[i]=f[i-1]+a[i]+ans;
                if(fa[a[i]]==i-1)
                dp[i]=dp[i]+a[i];
            }
            else
            {
                dp[i]=dp[i-1];
                ha[a[i]]=T+1;
            }
            long long cs=dp[i]-f[i];
            if(a[i]==a[i+1])
            cs-=a[i];
            add(1,M,1,a[i],cs,i);
            prt=max(prt,dp[i]);
        }
        cout<<prt<<endl;
    }
    return 0;
}